package leetcode_day._2021._202106._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/18 22:38
 * 最小进制
 * 算法：数学
 * 1、由进制越大，1 的数量越少可得，要使获得的进制小，那么长度就要长
 * 2、获得要求数字的 1 的最大长度，即进制为 2 的时候，求得长度，使用换底公式，进制位不一定都要为 1
 * 比如 4 的二进制位数为 3
 * 3、当知道 len 后，如何得出 k
 * s = len - 1
 * (n)10 = (11..1)k = k^0 + k^1 + ... + k^s) < C(s, 0)k^0 + C(s, 1)k^1 + ... + C(s, s)k^s = (1 + k)^s
 * 4、因为 (n)10 > k^s ==> k^s < (n)10 < (1 + k)^s ==> k < (n)^(1/s) < k + 1
 * 所以 k 为 (n)^(1/s) 取整
 * 二项式定理
 */
public class _18_483 {

    public String smallestGoodBase(String n) {
        long m = Long.parseLong(n);
        int max = (int) (Math.log(m) / Math.log(2) + 1);
        for (int i = max; i >= 3; i--) {
            int k = (int) Math.pow(m, 1.0 / (i - 1));
            long res = 0;
            for (int j = 0; j < i; j++) res = res * k + 1;
            if (res == m) return k + "";
        }
        return m - 1 + "";
    }

}
